import heapq
class Solution(object):
    def getBiggestThree(self, grid):
        m = len(grid)
        n = len(grid[0])
        pre1 = [[0 for _ in range(n)] for _ in range(m)]
        pre2 = [[0 for _ in range(n)] for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if i == 0 or j == 0:
                    pre1[i][j] = grid[i][j]
                else:
                    pre1[i][j] = pre1[i - 1][j - 1] + grid[i][j]
                if i == 0 or j == n - 1:
                    pre2[i][j] = grid[i][j]
                else:
                    pre2[i][j] = grid[i][j] + pre2[i - 1][j + 1]
        max_st = []
        for i in range(m):
            for j in range(n):
                k = 0
                while i + 2 * k < m and j - k >= 0 and j + k < n:
                    if k == 0:
                        if grid[i][j] not in max_st:
                            heapq.heappush(max_st, grid[i][j])
                            if len(max_st) > 3:
                                heapq.heappop(max_st)
                    else:
                        if i == 0:
                            bian1 = pre2[i + k][j - k]
                        else:
                            bian1 = pre2[i + k][j - k] - pre2[i - 1][j + 1]
                        bian2 = pre1[i + k][j + k] - pre1[i][j]
                        bian3 = pre1[i + 2 * k][j] - pre1[i + k][j - k]
                        bian4 = pre2[i + 2 * k][j] - pre2[i + k][j + k] - grid[i + 2 * k][j]
                        s = bian1 + bian2 + bian3 + bian4
                        if s not in max_st:
                            heapq.heappush(max_st, s)
                            if len(max_st) > 3:
                                heapq.heappop(max_st)
                    k += 1
        max_st.sort(reverse=True)
        return max_st

